class Solution {//leetcode79——单词搜索
private:
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0}; 
    bool dfs(const vector<vector<char>>&board,int col,int row,int pos,const string &key){
        if(pos==key.size()) return true;
        for(int i=0;i<4;i++)
        {
            int y=row+dy[i],x=col+dx[i];
            if(y>=0&&y<m&&x>=0&&x<n&&board[y][x]==key[pos]&&used[y][x]==false){
                used[y][x]=true;
                if(dfs(board,x,y,pos+1,key)) return true;
                used[y][x]=false;
            }
        }
        return false;
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
        m=board.size();
        n=board[0].size();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(board[i][j]==word[0])
                {
                    used[i][j]=true;
                    if(dfs(board,j,i,1,word)) return true;
                    used[i][j]=false;
                }
            }
        }
        return false;
    }
private:
    string path;
    bool used[6][6]={false};
    int m;
    int n;
};